package leetcode.code0041;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution41_1 implements IDebug {
	public int firstMissingPositive(int[] nums) {
		int len = nums.length;
		int l = 0;
		List<Integer> list = new ArrayList<>();
		while (l < len) {
			int num = nums[l];// 当前处理的位置是l,当前处理的数字是num
			int aim = num - 1;// num的目标是放在index位置上
			if (aim == l) {// 目标正好是当前位置,当前数字num妥投.
				l++;// 处理下一个
				continue;
			}
			if (num < 1 || num > len) {// 当前数字的目标不是一个有效整数,未在[1,len]内
				list.add(l + 1);
				l++;// 不需要投递,不管了,看下一个
			} else {
				if (num == nums[aim]) {// 当前数字的目标是一个有效整数,已放在目标位置上
					list.add(l + 1);
					l++;// 处理下一个
				} else {// 当前数字的目标是一个有效整数,未放在目标位置上
					if (list.indexOf(num) != -1) {
						list.remove(list.indexOf(num));
					}
					int temp = nums[aim];// 把目标位置数字缓存
					nums[aim] = num;// 当前位置妥投
					nums[l] = temp;// 目标位置上的原数字,作为当前处理数据,周而复始, l不能++
				}
			}
		}
		return list.isEmpty() ? l + 1 : list.get(0);
	}

	@Override
	public void debug1() {
		String str = "[1,2,0]";
		int e = 3;
		int r = this.firstMissingPositive(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[3,4,-1,1]";
		int e = 2;
		int r = this.firstMissingPositive(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String str = "[7,8,9,11,12]";
		int e = 1;
		int r = this.firstMissingPositive(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		String str = "[1]";
		int e = 2;
		int r = this.firstMissingPositive(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	public void debug5() {
		String str = "[1,1]";
		int e = 2;
		int r = this.firstMissingPositive(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	public void debug6() {
		String str = "[2,1]";
		int e = 3;
		int r = this.firstMissingPositive(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	public void debug7() {
		String str = "[2,2]";
		int e = 1;
		int r = this.firstMissingPositive(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	public void debug8() {
		String str = "[0,2,2,4,0,1,0,1,3]";
		int e = 5;
		int r = this.firstMissingPositive(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	public void debug9() {
		String str = "[1,4,2,0,3,4,2,4,2]";
		int e = 5;
		int r = this.firstMissingPositive(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	public static void main(String[] args) {
		Solution41_1 so = new Solution41_1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
		so.debug8();
		so.debug9();
	}

}
